1. Field of the Invention
The present invention pertains to the field of processing image data to generate useful groupings and partitioning within an image. Specifically, the present invention pertains to grouping images on an electronic work surface, generating regions according to the groupings, and dividing the electronic work using borders according to the regions.
2. Discussion of the Related Arts
Previous electronic work surface implementations include a pen-based system in which users can explicitly create borders one at a time on an electronic work surface. These borders include structured borders-straight line segments that tessellate the work surface into rectangular regions and freeform linear or enclosure borders which are freehand drawn straight lines and loop-shaped curves. The amount of a human user""s time required to enter and edit such user-created borders is significant. Moreover, human error often brings the appropriateness of the user-created borders into question and requires his editing of the borders. As is apparent from the above discussion, it would be desirable to automatically generate the borders from an input array to save the user time and increase the precision with which the borders are generated.
Conventionally, users can explicitly create borders one at a time using a border creation gesture. The spatial separation between clusters of objects on the work surface often matches the user""s perception of where to place the borders. The present invention presents image analysis methods for automatically generating structured, enclosure, and freeform borders that correspond closely to the borders that a human user would create based upon the same input image.
According to an aspect of the present invention, the spatial separations between clusters of objects on the electronic work surface are analyzed to automatically generate borders. The borders created according to the methods of the present invention are believed to resemble the borders that would be created by human users based upon their perception of the same input image.
The borders according to the present invention can be utilized in at least two manners. The borders may become explicit editable borders within an output image having the benefit that the automatic generation of the editable borders saves the user the time and effort of creating them himself. Alternatively, the borders created may be implicit ephemeral borders which free the user from having to delimit the structures unnecessarily and provide feedback during the course of a structured operation such as list operations. The image analysis methods according to the present invention comprises several aspects of transformations of image data.
According to an aspect of the present invention, a method defines regions that correspond roughly to lines of handwritten or typeset text on the electronic work surface. This method according to the present invention accepts an image array as input and produces a text lines array output. This method uses the sufficient stability grouping technique to determine grouping of elements in the input image array into the text lines in the output text lines array.
According to another aspect of the present invention, a method takes the text lines array as input and creates a text regions array. In this method, the text lines are expanded into regions corresponding roughly to the level of paragraphs. This method uses the sufficient stability grouping technique to determine the amount of vertical expansion to apply to each text line so as to create text regions in the output array which correspond to the text lines in the input text lines array.
According to yet another aspect of the present invention, a method takes the text regions array as input and extracts enclosure borders from the text regions. The method according to this aspect of the present invention applies distance thresholding and edge labeling based upon the contents of the text lines array.
According to still another aspect of the present invention, a method extracts structured borders from the text regions array. Structured borders are straight horizontal and vertical lines which divide the electronic work surface into rectangular spaces, in which each rectangular space in the structured borders array corresponds to a text region in the text regions array. The method according to this aspect of the present invention applies two-dimensional projection operations based upon the contents of the text lines array.
According to yet still another aspect of the present invention, a method extracts freeform linear borders from the text regions array. Freeform linear borders divide the electronic work surface into connected areas, in which each connected area in the freeform linear borders array corresponds to a text region in the text regions array. The freeform linear borders result from a Voronoi tesselation performed upon the contents of text regions array.
These and other aspects, features, and advantages of the present invention are fully described in the Detailed Description of the Invention and illustrated in the Figures.